package two.chapter_4.c4_1;

import edu.princeton.cs.algs4.In;
import two.chapter_1.c1_3.Bag;

/**
 * 邻接表数组实现的图
 */
public class AdjGraph implements Graph{
    private Bag<Integer> [] adj;
    private int v;//顶点数
    private int e;//边数
    public AdjGraph(int v){
        this.v=v;
        adj=new Bag[v];
        for (int i=0;i<v;i++){
            adj[i]=new Bag<>();
        }
    }
    public AdjGraph(In in){
        this(in.readInt());
        int edges=in.readInt();
        for (int i=0;i<edges;i++){
            int v=in.readInt();
            int w=in.readInt();
            addEdge(v,w);
        }
    }
    @Override
    public int v() {
        return v;
    }

    @Override
    public int e() {
        return e;
    }

    @Override
    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
        e++;
    }

    @Override
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }

    @Override
    public String toString() {
       String s=v+" vertices, "+e+" edges\n";
       for (int i=0;i<v;i++){
           s+=i+"：";
           for (int w:this.adj(i)){
               s+=w+" ";
           }
           s+="\n";
       }
       return s;
    }
}
